package com.dynamicprogram;

import java.util.List;

public class Solution931 {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        System.arraycopy(matrix[0], 0, dp[0], 0, n);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = matrix[i][j] + dp[i - 1][j];
                if (j + 1 < n) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j + 1] + matrix[i][j]);
                if (j - 1 >= 0) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
            }
        }
        int res = Integer.MAX_VALUE;
        for (int x : dp[n - 1]) {
            res = Math.min(res, x);
        }
        return res;
    }
}
